package codingforgreat.lchot150;

public class Lc098 {
  public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
    public boolean isValidBST(TreeNode root) {
        return func(root).is;
    }
    public class Info{
        int max;
        int min;
        boolean is;
        public Info(int max,int min,boolean is){
            this.max = max;
            this.min = min;
            this.is = is;
        }
    }
    public Info func(TreeNode node){
        if(node == null){
            return  null;
        }
        Info left =  func(node.left);
        Info right = func(node.right);
        boolean is = false;
        if((left==null && right == null) || ( ((left == null && right.is) ||(right == null && left.is)) && ((right == null && left.max < node.val) ||  (left==null && right.min > node.val)))  ){
            is = true;
        }
        else if(left != null && right != null && left.is && right.is && left.max < node.val && right.min > node.val){
            is = true;
        }
        int min = 0;
        int max = 0;
        if(left != null && right != null){
            min = Math.min(node.val,Math.min(left.min,right.min));
            max = Math.max(node.val,Math.max(left.max,right.max));
        }else
        if(left == null && right == null){
            min = node.val;
            max = node.val;
        }else
        if(left == null && right != null){
            max = Math.max(right.max,node.val);
            min = Math.min(right.min,node.val);
        }else
        if(right == null && left != null){
            max = Math.max(left.max,node.val);
            min = Math.min(left.min,node.val);
        }

        return new Info(max,min,is);
    }
    public boolean isValidBST2(TreeNode root) {
        TreeNode cur = root;
        TreeNode mostRight = null;
        Integer pre = null;
        boolean ans = true;
        while(cur != null){
            mostRight = cur.left;
            if(mostRight != null){
                while(mostRight.right != null && mostRight.right != cur){
                    mostRight = mostRight.right;
                }
                if(mostRight.right == null){
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                }else{
                    mostRight.right = null;
                }
            }
            if(pre != null && pre >= cur.val){
                ans = false;
            }
            pre = cur.val;
            cur = cur.right;
        }
        return ans;
    }
}
